99. 恢复二叉搜索树

Similar Question

leading to the advanced question

Solution Tips

方案一: 中序遍历

const swap = (x, y) => {
    const temp = x.val;
    x.val = y.val;
    y.val = temp;
}

var recoverTree = function(root) {
    const stack = [];
    let x = null, y = null, pred = null;

    while (stack.length || root !== null) {
      while (root !== null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      if (pred !== null && root.val < pred.val) {
        y = root;
        if (x === null) {
            x = pred;
        }
        else break;
      }
      pred = root;
      root = root.right;
    }
    swap(x, y);
};